This invention relates to a digital signature method of realizing a signature and seal function for digital plaintexts, a digital signature system constructed using the digital signature method, and a program storage device in which a program concerning the digital signature method has been stored.
Various methods of generating digital signatures have been proposed. Typical ones of them are a method based on the difficulty of the problem of factorization into prime factors and a method based on the difficulty of a discrete logarithm problem. The method based on a discrete logarithm problem includes a method using a multiplicative group over an ordinary finite field and a method using an additive group on an elliptic curve. It is said that a discrete logarithm problem in an additive group on an elliptic curve is safer than a discrete logarithm problem in a multiplicative group over an ordinary finite field or the problem of factorization into prime factors, since a method of solving the former efficiently has not been found.
It is known that when a digital signature or a public key cryptosystem is composed with the same security, a system based on a discrete logarithm problem on an elliptic curve enables the size of a parameter to be set smaller than a system based on another problem, which leads to the effect of reducing the amount of processing.
When the characteristic of a finite field Fq is neither 2 or 3, an elliptic curve E/Fq over the finite field Fq is defined by parameter a and parameter b and finite field Fq in the following equation (1):
y 2=x 3+ax+b (a, b, x, and y are elements of the finite field Fq) (1)
where y 2 represents the square of y and x 3 denotes the cube of x. Hereinafter, x a indicates raising x to the a-th power.
The elements of the elliptic curve E/Fq consist of pairs of (x, y) meeting equation (1) (these pairs are referred to as points on the elliptic curve) and a point at infinity O. The point at infinity O cannot be expressed in the form of a pair (x, y) of elements of the finite field Fq. In practical use, however, a one-bit flag representing the point at infinity has only to be provided. It is known that a set of points on the elliptic curve forms a group for addition. Regarding the addition, the point at infinity makes an identity element.
A more detailed explanation of an elliptic curve E/Fq and the definition of addition have been given in, for example, Koblitz, "A Course in Number Theory and Cryptography," Springer-Verlag. Hereinafter, unless otherwise specified, capital letters represent points (i.e., pairs of elements over a finite field Fq or a point at infinity) and small letters denote elements of a finite field Fq or natural numbers. The finite field Fq is made up of as many elements as q=p t gives (where p is a prime number and t is a positive integer). For example, typical examples of the finite field Fq are a prime field Zp (composed of integers ranging from 0 to p-1) and a 2's extension field GF of (2 t).
One typical digital signature scheme on an elliptic curve is an ElGamal signature on an elliptic curve. The method uses finite fields Fq, a, and b defining an elliptic curve, a base point G, and the order z of the base point G as a public key. The order z of the base point G is the smallest positive integer that meets the following: z.multidot.G=O (infinity) over E/Fq.
The secret key for the signature generator is an integer x relatively prime to and less than the order z and the public key for the signature generator is the following point Y: EQU Y=x.multidot.G over E/Fq
A digital signature for an integer m (which is generally digest information obtained by calculating plaintext data M expressed in digital bit strings using a cryptographic hash function) depending only on plaintext data M is generated by the following procedure. First, a random number k, a natural number relatively prime to and less than the order z, is determined and from the k, R in the following equation is found: EQU R=k.multidot.G over E/Fq
Next, using a function f that converts the point data on the elliptic curve into natural numbers in Zz (the natural numbers equal to or less than z-1), r is found: EQU r=f(R)
For example, a hash function may be used.
Further, the following s is found: EQU s=(m-x.multidot.r)/k(mod z)
The signature data is a pair of (R, s). The verification of the signature is carried out by checking to see if m, R, and s fulfill the following equation: EQU r=f(R) EQU m.multidot.G=r.multidot.Y+s.multidot.R over E/Fq
The ElGamal signature scheme has been written in detail in "T. ElGamal," "A public key cryptosystem and a signature scheme based on discrete logarithms," IEEE Trans. IT, Vol. IT-31, No. 4, July 1985, pp. 469-472.
The aforementioned signature scheme can realize the function of sealing an ordinary electronic document. In addition to this, the function of allowing more than one signer to seal an electronic circular document is also wanted. Such a function can be constructed by concatenating the signature data items by more than one signer concerning the same document. The construction, however, has a disadvantage in that as the number of signers increases, the amount of signature data and the amount of processing needed in checking a signature increase accordingly. A scheme by which the increase of the signature data size is minimized or a scheme by which the amount of processing required in checking a signature is suppressed, as compared with a scheme by which signatures are simply concatenated, has been proposed. They are called multisignature schemes.
The multisignature schemes, however, have not used the ElGamal signature scheme based on the difficulty of a discrete logarithm problem on an elliptic curve.